`
https://leetcode.cn/problems/min-cost-to-connect-all-points/
`

/**
 * @param {number[][]} points
 * @return {number}
 */
var minCostConnectPoints = function (points) {
  const n = points.length

  const edges = []
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const x1 = points[i][0], y1 = points[i][1]
      const x2 = points[j][0], y2 = points[j][1]
      edges.push([i, j, Math.abs(x1 - x2) + Math.abs(y1 - y2)])
    }
  }

  // 按权重排序边
  edges.sort((a, b) => a[2] - b[2])

  let weightCount = 0
  const uf = new UF(n)
  for (const edge of edges) {
    const u = edge[0]
    const v = edge[1]
    const weight = edge[2]
    // 若这条边会产生环，则不能加入
    if (uf.connected(u, v)) {
      continue
    }
    // 若这条边不会产生环，则属于最小生成树
    weightCount += weight
    uf.union(u, v)
  }

  return weightCount
};

class UF {
  // n 为图中节点的个数
  constructor(n) {
    // 连通分量个数
    this._count = n
    // 存储每个节点的父节点
    this.parent = Array.from({ length: n }, (_, index) => index)
  }

  // 将节点 p 和节点 q 连通
  union(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)

    if (rootP === rootQ) {
      return
    }

    this.parent[rootQ] = rootP
    // 两个连通分量合并成一个连通分量
    this._count--
  }

  // 判断节点 p 和节点 q 是否连通
  connected(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)
    return rootP === rootQ
  }

  // 返回图中的连通分量个数
  count() {
    return this._count
  }

  _find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this._find(this.parent[x])
    }
    return this.parent[x]
  }
}